#pragma once

#include <iostream>
#include <cstring>
#include <vector>
#include <functional>
using namespace std;

template <class T, class Container = vector<T>, class Compare = less<T>>
class priority_queue
{
public:
    priority_queue() = default;

    template <class InputIterator>
    priority_queue(InputIterator first, InputIterator last)
    {
        InputIterator it = first;
        while (it != last)
        {
            c.push_back(*it);
            ++it;
        }
    }
    bool empty() const
    {
        return c.empty();
    }
    size_t size() const
    {
        return c.size();
    }
    const T& top() const
    {
        return c.front();
    }
    void push(const T& x)
    {
        c.push_back(x);
        AdjustUp(c.size() - 1);
    }
    void pop()
    {
        swap(c[0], c[c.size() - 1]);
        c.pop_back();
        AdjustDown(0);
    }
private:
    void AdjustUp(int child)
    {
        int parent = (child - 1) / 2;
        while (parent > child)
        {
            if (Com(c[parent], c[child]))
            {
                swap(c[parent], c[child]);
            }
            child = parent;
            parent = (child - 1) / 2;
        }
    }
    void AdjustDown(int parent)
    {
        int n = c.size();
        int child = parent * 2 + 1;
        while (child < n)
        {
            if (child + 1 < n && Com(c[child], c[child + 1]))
            {
                ++child;
            }
            if (Com(c[parent], c[child]))
            {
                swap(c[child], c[parent]);
            }
            parent = child;
            child = parent * 2 + 1;
        }
    }
private:
    Container c;
    Compare Com;
};